package com.zyk.problem;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class LongestCommonSubString {

    // 全排列匹配, n*n个字符比较, 比较的过程是每个字符全排列和n个字符做匹配*n(匹配过程认为是(字符长度), 因为用的indexOf实现的)
    // 所以时间复杂度为: O(n^4 * m!)    即n的4次方 * 每个字符的全排列
    public static String longestSubString(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String ans = "";
        for (String str : strs) {
            for (int i = 0; i < str.length(); i++) {
                for (int j = 1; j < str.length() - i + 1; j++) {
                    if (j > ans.length() && validate(str.substring(i, i + j), strs)) {
                        ans = str.substring(i, i + j);
                    }
                }
            }
        }
        return ans;
    }

    private static boolean validate(String substring, String[] strs) {
        if (substring.length() < 1) {
            return false;
        }
        for (String s : strs) {
            if (!s.contains(substring)) {
                return false;
            }
        }
        return true;
    }


    // 暴力尝试
    // 第一个字符和后序所有字符比较, 比较过程是两个字符串的长度即 s1Len*s2Len
    // 时间复杂度(n * m^2)
    public static String longestCommonSubstring(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        if (strs.length < 2) return strs[0];
        countMap = new HashMap<>();
        for (int i = 1; i < strs.length; i++) {
            longestCommonSubstring(strs[0], strs[i]);
        }
        int N = strs.length;
        String ans = "";
        for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() == N - 1) {
                if (entry.getKey().length() > ans.length()) {
                    ans = entry.getKey();
                }
            }
        }
        return ans;
    }

    static Map<String, Integer> countMap;

    public static void longestCommonSubstring(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int R = str1.length, C = str2.length;
        int[][] dp = new int[R + 1][C + 1];
        HashSet<String> set = new HashSet<>();
        for (int i = R - 1; i >= 0; i--) {
            for (int j = C - 1; j >= 0; j--) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = 1 + dp[i + 1][j + 1];
                    String subStr = s1.substring(i, i + dp[i][j]);
                    if (!set.contains(subStr)) {
                        for (int k = 1; k <= subStr.length(); k++) {
                            String subsubStr = subStr.substring(0, k);
                            if (!set.contains(subsubStr)) {
                                countMap.put(subsubStr, countMap.getOrDefault(subsubStr, 0) + 1);
                                set.add(subsubStr);
                            }
                        }
                    }
                }
//                else dp[i][j] = 0;
            }
        }
    }


    // 暴力尝试, 两个字符串的最长公共子串
    public static int longestCommonSubstring1(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int ans = -1;
        for (int i = 0; i < str1.length; i++) {
            for (int j = 0; j < str2.length; j++) {
                ans = Math.max(ans, process(str1, str2, i, j));
            }
        }
        return ans;
    }

    public static int process(char[] s1, char[] s2, int i, int j) {
        if (i == s1.length || j == s2.length) {
            return 0;
        } else if (s1[i] == s2[j]) {
            return 1 + process(s1, s2, i + 1, j + 1);
        } else {
            return 0;
        }
    }

    // for test
    public static void main(String[] args) {
//        String[] strs = {
//                "flower", "flow", "flight"
//        };

//        String[] strs = {
//                "dog", "racecar", "car"
//        };

        /*String[] strs = {
                "BAAEE", "CEBCB", "EBDAD", "EECDE", "EAEAA", "BBACA", "ECBBE", "EDAAD"
        };
        long s1 = System.nanoTime();
        String ans1 = longestCommonSubstring(strs);
        long s2 = System.nanoTime();
        String ans2 = longestSubString(strs);
        long s3 = System.nanoTime();

        System.out.println(ans1 + ": " + (s2 - s1));
        System.out.println(ans2 + ": " + (s3 - s2));*/


        int times = 10000;
        int maxLen = 1000;
        int maxValueLen = 1000;
        for (int i = 0; i < times; i++) {
            System.out.println("==============================");
            String[] strs = generate(maxLen, maxValueLen);
            long s1 = System.currentTimeMillis();
            String ans1 = longestCommonSubstring(strs);
            long s2 = System.currentTimeMillis();
            String ans2 = longestSubString(strs);
            long s3 = System.currentTimeMillis();
            if (!ans1.equals(ans2) && ans1.length() != ans2.length()) {
                System.out.println("OOPS!");
                System.out.println(Arrays.toString(strs));
                System.out.println("暴力解: " + ans1);
                System.out.println("匹配: " + ans2);
                break;
            }
            System.out.println("暴力解: " + (s2 - s1));
            System.out.println("匹配: " + (s3 - s2));
            System.out.println("===============================");
        }
    }

    public static String[] generate(int maxLen, int maxValueLen) {
        maxLen = (int) (Math.random() * maxLen);
        String[] res = new String[maxLen];
        for (int i = 0; i < maxLen; i++) {
            char[] str = new char[maxValueLen];
            for (int j = 0; j < str.length; j++) {
                str[j] = (char) (Math.random() * 5 + 'A');
            }
            res[i] = new String(str);
        }
        return res;
    }

}
